import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * @Author: wanqian
 * @Date: 2021/3/1 7:22
 */
public class GreedyAlgorithm {
    public static void main(String[] args) {
        // 创建广播电台,放入到Map
        HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
        // 加入到map
        broadcasts.put("K1", new HashSet<String>() {
            {
                add("北京");
                add("上海");
                add("天津");
            }
        });
        broadcasts.put("K2", new HashSet<String>() {
            {
                add("广州");
                add("北京");
                add("深圳");
            }
        });
        broadcasts.put("K3", new HashSet<String>() {
            {
                add("成都");
                add("上海");
                add("杭州");
            }
        });
        broadcasts.put("K4", new HashSet<String>() {
            {
                add("上海");
                add("天津");
            }
        });
        broadcasts.put("K5", new HashSet<String>() {
            {
                add("杭州");
                add("大连");
            }
        });

        // allAreas 存放所有的地区
        HashSet<String> allAreas = new HashSet<>();
        for (Map.Entry<String, HashSet<String>> broadcast : broadcasts.entrySet()) {
            allAreas.addAll(broadcast.getValue());
        }

        // 创建ArrayList, 存放选择的电台集合
        ArrayList<String> selects = new ArrayList<>();

        int maxCount;
        int count;
        String maxKey;
        while (allAreas.size() != 0) {
            //初始化
            maxCount = 0;
            maxKey = null;
            //每次while循环遍历所有广播站
            for (String broadCast : broadcasts.keySet()) {
                //取出当前广播站覆盖城市
                HashSet<String> cities = broadcasts.get(broadCast);
                //剩余城市中所覆盖的城市 取交集
                cities.retainAll(allAreas);
                //覆盖数量
                count = cities.size();
                //若覆盖更广则更新
                if (count > maxCount) {
                    maxKey = broadCast;
                    maxCount = count;
                }
            }
            //加入广播站并删除已覆盖城市
            if (maxKey != null) {
                selects.add(maxKey);
                allAreas.removeAll(broadcasts.get(maxKey));
            }
        }
        System.out.println(selects);
    }
}
